#include <bits/stdc++.h>

#define in read()
#define fi first
#define se second
#define pb push_back

using namespace std;

typedef long long ll;
typedef double db;
typedef vector < int > vec;
typedef pair < int , int > pii;

int read() {
    int x = 0; bool f = 0; char ch = getchar(); while(!isdigit(ch)) f |= ch == '-',ch = getchar();
    while(isdigit(ch)) x = x * 10 + (ch ^ 48),ch = getchar(); return f ? -x : x;
}

const int N = 3e4 + 10;

int n;
char s[N];

struct SA {
    int ht[N],rk[N],ork[N << 1],px[N],id[N],cnt[N],m,pw[20],lg[N],sa[N];
    int mn[20][N];
    void buildst() {
	memset(mn,0x3f,sizeof mn);
	for(int i = 1;i <= n;i++) mn[0][i] = ht[i];
	for(int i = 2;i <= n;i++) lg[i] = lg[i >> 1] + 1;
	for(int i = (pw[0] = 1);i < 20;i++) pw[i] = pw[i - 1] * 2;
	for(int i = 1;i < 20;i++)
	    for(int j = 1;j + pw[i] - 1 <= n;j++)
		mn[i][j] = min(mn[i - 1][j],mn[i - 1][j + pw[i - 1]]);
    }
    int query(int x,int y) {
	int l = min(rk[x],rk[y]) + 1,r = max(rk[x],rk[y]);
	int k = lg[r - l + 1]; return min(mn[k][l],mn[k][r - pw[k] + 1]);
    }
    void build(char *s) {
	m = 300; for(int i = 1;i <= n << 1;i++) ork[i] = 0;
	for(int i = 1;i <= m;i++) cnt[i] = 0;
	for(int i = 1;i <= n;i++) ++cnt[rk[i] = s[i]];
	for(int i = 1;i <= m;i++) cnt[i] += cnt[i - 1];
	for(int i = n;i >= 1;i--) sa[cnt[rk[i]]--] = i;
	for(int h = 1,p;h <= n;h <<= 1,m = p) {
	    p = 0; for(int i = n;i > n - h;i--) id[++p] = i;
	    for(int i = 1;i <= n;i++) if(sa[i] > h) id[++p] = sa[i] - h;
	    for(int i = 1;i <= m;i++) cnt[i] = 0;
	    for(int i = 1;i <= n;i++) ++cnt[px[i] = rk[id[i]]];
	    for(int i = 1;i <= m;i++) cnt[i] += cnt[i - 1];
	    for(int i = n;i >= 1;i--) sa[cnt[px[i]]--] = id[i];
	    for(int i = 1;i <= n;i++) ork[i] = rk[i];
	    auto cmp = [&] (int a,int b) { return ork[a] == ork[b] && ork[a + h] == ork[b + h]; };
	    p = 0; for(int i = 1;i <= n;i++) rk[sa[i]] = cmp(sa[i],sa[i - 1]) ? p : ++p;
	} 
	for(int i = 1,j = 0;i <= n;i++) {
	    if(j) j--; while(s[i + j] == s[sa[rk[i] - 1] + j]) j++;
	    ht[rk[i]] = j;
	}
	buildst();
    }
}A,B;

int f[N],g[N];

void solve() {
    scanf("%s",s + 1); n = strlen(s + 1); A.build(s); reverse(s + 1,s + n + 1); B.build(s);
    for(int i = 0;i <= n;i++) f[i] = g[i] = 0;
    for(int len = 1;len <= n / 2;len++)
	for(int i = len,j = len + len;j <= n;i += len,j += len) {
	    int lcp = min(len,A.query(i,j)),lcs = min(B.query(n - i + 2,n - j + 2),len - 1);
	    if(lcp + lcs >= len) {
		int mor = lcp + lcs - len;
		f[i - lcs]++; f[i - lcs + mor + 1]--;
		g[j + lcp - mor - 1]++; g[j + lcp]--;
	    }
	}
    ll ans = 0;
    for(int i = 1;i <= n;i++) f[i] += f[i - 1],g[i] += g[i - 1];
    for(int i = 1;i < n;i++) ans += (ll) g[i] * f[i + 1];
    printf("%lld\n",ans);
}


int main() {
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
#endif
    for(int T = in;T;T--) solve();
}
